package top.interview

import java.util.Collections

import problem.Problem

class Q887SuperEggDrop extends Problem {

  def superEggDrop(K: Int, N: Int): Int = {
    val a = Array.ofDim[Int](N, K)
    for {
      i <- 1 to N
      j <- 1 to K
    } {
      f(i, j, a)
    }
    f(N, K, a)
  }

  def f(n: Int, k: Int, a: Array[Array[Int]]): Int = {
    if (k == 0 || n == 0) 0
    else if (n == 1) 1
    else if (k == 1) n
    else if (a(n - 1)(k - 1) != 0) a(n - 1)(k - 1)
    else {
      val v = (1 to n).map { x =>
        math.max(f(n - x, k, a), f(x - 1, k - 1, a))
      }.min

      a(n - 1)(k - 1) = v + 1

      v + 1
    }
  }

  override def test(): Unit = {

    val cases = Table(("K", "N", "steps"),
      (1, 2, 2),
      (2, 6, 3),
      (3, 14, 4)
    )

    println(superEggDrop(10, 10000))

    forAll(cases) { case (k, n, steps) =>
      superEggDrop(k, n) shouldBe steps
    }
  }
}
